package h0910;

import java.util.*;

/**
  * @description 前k个高频单词
  * @author 不知名帅哥
  * @date 2024/9/10 22:41
  * @version 1.0
*/
public class FirstKFrequencyWord {
    public static void main(String[] args) {

    }
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
        }
        List<String>[] buckets=new List[words.length+1];
        for (String s : map.keySet()) {
            Integer frequence = map.get(s);
            if (buckets[frequence]==null){
                buckets[frequence]=new ArrayList<>();
            }
            buckets[frequence].add(s);
        }
        List<String> res=new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0&&res.size()<k; i--) {
            if (buckets[i]!=null){
                Collections.sort(buckets[i]);
                res.addAll(buckets[i]);
            }
        }
        return res.subList(0,k);
    }

    public List<String> topKFrequent2(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
        }
        PriorityQueue<String> queue = new PriorityQueue<>((o1, o2) -> {
            int a = map.get(o1);
            int b = map.get(o2);
            if (a != b){
                return a-b;
            }else {
                return o2.compareTo(o1);
            }
        });
        for (String s : map.keySet()) {
            queue.offer(s);
            if (queue.size()>k){
                queue.poll();
            }
        }
        List<String> list = new ArrayList<>(queue.stream().toList());
        Collections.reverse(list);
        return list;
    }
}
